题解 CF1375F@洛谷 | 1375F@Codeforces 【Integer Game】

题意：交互题，三堆石子，石子个数分别为 $a,b,c\in\left[1,10^9\right]\cap\rm{Z}$ ，选择先手或者后手进行游戏。先手给定一个数 $k\in\left[1,10^{12}\right]\cap\rm{Z}$ ，后手将一堆石子个数增加 $k$ ，不能连续增加同一堆两次。如果有两堆石子个数一样，后手输；如果 $10^3$ 次内先手没有赢，则后手赢。问谁有必胜策略。

首先，我们考虑什么时候后手会输。

假设此时 $a\lt b\lt c$ ：

如果 $b-a\ne c-b$ ，则不论可以修改哪个，后手均不会输。
如果 $b-a=c-b$ ，此时如果不能修改 $c$ ，则可以构造出 $k=b-a=c-b$ 使得后手必败；如果可以修改 $c$ ，则不能保证。

得出结论：当且仅当 $a,b,c$ 成等差数列，且最大数不能被修改时后手败。

我们考虑是否能构造一种方法，使得在若干步后，三堆石子满足这一条件。

考虑如何能得到等差数列，且最大数不能修改？设原来三堆石子为 $a\lt b\lt c$ 且 $x=c-b,y=c-a$ ，并且最大数不能被修改，那么就可以构造 $k=x+y=c\times 3-(a+b+c)$ 满足条件。

为啥？假设修改 $a$ ，则三个数变为 $a+c\times 3-(a+b+c),b,c$ ，即为 $2\times c-b,b,c$ ，其中 $(2\times c-b)-c=c-b$ ，符合上面的描述。修改 $b$ 同理。

此时我们发现，中位数为 $c$ ，即原来的最大数；公差可以根据这一点推出：用 $c$ 减去另一个没有变化的数。

问题转化为如何固定最大值不能动。我们一开始构造 $k=\inf$ ，即大于任何一个数的数，此时被修改的不管是哪个，都是修改后的最大值。记录这个最大值，然后按照上面说的做即可。

总结：首先构造 $k=\inf$ ，获得最大值位置，用指针记录。然后根据最大值，构造 $k=c\times 3-s$ ，其中 $c$ 为这个最大值， $s$ 为三个数的和。最后得到一个最大数不能修改的等差数列，构造 $k$ 为公差即可。

~~没错你没看错，先手在三步以内必胜。~~

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e10;

ll a[3], *p, k, s;
ll interact(ll x) {
	printf("%lld\n", x);
	fflush(stdout);
	ll res;
	scanf("%lld", &res);
	if(!res) exit(0);
	a[--res] += x;
	return res;
}

int main() {
	scanf("%lld%lld%lld", &a[0], &a[1], &a[2]);
	puts("First"); fflush(stdout);
	s = a[0] + a[1] + a[2] + inf;
	k = interact(inf);
	p = &a[k];
	k = interact((*p)*3-s);
	ll _ = 3 - (p - a) - k;
	k = interact((*p)-a[_]);
	return 0;
}